/**
 * Created by ospip on 2017/9/19.
 * Copyright (c) 2017 LLAP. All rights reserved.
 */
public class DoublyList<T extends Comparable<? super T>> {

    private static class Node<T extends Comparable<? super T>> implements Comparable<Node<T>> {
        public T data;
        public Node<T> prev, next;

        public Node(T data, Node<T> prev, Node<T> next) {
            this.data = data;
            this.prev = prev;
            this.next = next;
        }

        public Node() {
            this(null, null, null);
        }

        @Override
        public String toString() {
            if (this.data == null) return "Null";
            return this.data.toString();
        }

        @Override
        public boolean equals(Object obj) {
            if (this.data == null && ((Node<T>)obj).data == null) return true;
            if (this.data == null || ((Node<T>)obj).data == null) return false;
            return obj == this || obj instanceof Node<?> && this.data.equals(((Node<T>) obj).data);
        }

        @Override
        public int compareTo(Node<T> t) {
            return this.data.compareTo(t.data);
        }
    }

    private static class Pair<T extends Comparable<? super T>> {
        public Node<T> first, second;
        public Pair(Node<T> a, Node<T> b) {
            this.first = a;
            this.second = b;
        }
        public Pair() {
            this(null, null);
        }
    }

    public Node<T> head, rear;

    public DoublyList() {
        this.head = new Node<T>();
        this.rear = new Node<T>(null, this.head, null);
        this.head.next = this.rear;
    }

    public DoublyList(T[] values) {
        this();
        for (T i : values) this.insert(i);
    }

    public DoublyList(DoublyList<T> src) {
        this();
        Node<T> t = src.head.next;
        while (t != src.rear) {
            this.insert(t.data);
            t = t.next;
        }
    }

    public void insert(T value) {                   // 尾插入
        this.insertPrev(value, rear);
    }

    public void insertPrev(T value, Node<T> s) {    // 节点前插入
        Node<T> t = new Node<>(value, s.prev, s);
        t.prev.next = t;
        s.prev = t;
    }

    public void insertNext(T value, Node<T> s) {    // 节点后插入
        Node<T> t = new Node<>(value, s, s.next);
        t.next.prev = t;
        s.next = t;
    }

    public void remove(Node<T> target) {
        target.prev.next = target.next;
        target.next.prev = target.prev;
        target.next = target.prev = null;
    }

    public void set(Node<T> target, T value) {
        target.data = value;
    }

    public void clear() {
        this.head.next = rear;
        this.rear.prev = head;
    }

    public void swap(Node<T> a, Node<T> b) {
        if (a == this.head || b == this.head || a == this.rear || b == this.rear) return;
        Node<T> al = a.prev, ar = a.next, bl = b.prev, br = b.next;
        al.next = ar.prev = b;
        bl.next = br.prev = a;
        a.next = br;
        a.prev = bl;
        b.next = ar;
        b.prev = al;
    }

    public int length() {
        int len = 0;
        Node<T> t = this.head.next;
        while(t != rear) {
            ++len;
            t = t.next;
        }
        return len;
    }

    @Override
    public String toString() {
        String ret = "<DoublyList [";
        Node<T> t = this.head.next;
        int len = 0;
        while(t != rear) {
            ret += t.toString();
            ++len;
            if (t != rear.prev) ret += ", ";
            t = t.next;
        }
        ret += "](" + len + ")>";
        return ret;
    }

    @Override
    public boolean equals(Object list) {
        if (!(list instanceof DoublyList<?>)) return false;
        if (((DoublyList<T>)list).head == this.head) return true;
        for (Node<T> t1 = this.head.next, t2 = ((DoublyList<T>)list).head.next; t1 != null && t2 != null; t1 = t1.next, t2 = t2.next) {
            if (!t1.equals(t2)) return false;
        }
        return true;
    }

    /*public Pair<T> search(DoublyList<T> pattern) {
        return this.search(pattern, this.head);
    }

    public Pair<T> search(DoublyList<T> pattern, Node<T> start) {
        Node<T> pos = start, tPos, cPos;
        Pair<T> ret = new Pair();
        while(pos != this.rear) {
            //System.out.println("Reading " + pos);
            if (pos.equals(pattern.head.next)) {
                //System.out.println("start from " + pos);
                ret = pos;
                for (tPos = pattern.head.next.next, cPos = pos.next; cPos != this.rear && tPos != pattern.rear; cPos = cPos.next, tPos = tPos.next) {
                    //System.out.println("pattern pos: " + cPos);
                    if (!tPos.equals(cPos)) {
                        cPos = null;
                        break;
                    }
                }
                if (cPos == this.rear && tPos != pattern.rear) cPos = null;
                if (cPos != null) {
                    return ret;
                }
            }
            pos = pos.next;
        }
        return ret;
    }

    public DoublyList<T> replace(DoublyList<T> pattern, DoublyList<T> list) {
        Node<T> pos, start, end;
        Pair<T> res;
        res = this.search(pattern, this.head);
        while (pos != null) {
            start = pos.prev;
        }
        return this;
    }*/
    /**
     * 替换所有与pattern匹配的子表为list
     * @param pattern
     *        需要匹配的子表
     * @param list
     *        需要替换成的表
     */
    public DoublyList<T> replaceAll(DoublyList<T> pattern, DoublyList<T> list) {
        //if (pattern.length() > this.length()) return this;
        Node<T> pos = this.head.next, startPos, cPos, tPos/*, nextPos = null*/;
        while(pos != this.rear) {
            if (pos.data.equals(pattern.head.next.data)) {
                startPos = pos.prev;
                for (tPos = pattern.head.next.next, cPos = pos.next; cPos != this.rear && tPos != pattern.rear; cPos = cPos.next, tPos = tPos.next) {
                    //if (cPos.equals(pattern.head.next) && nextPos == null) nextPos = cPos.prev;
                    if (!tPos.equals(cPos)) {
                        startPos = null;
                        break;
                    }
                }
                if (cPos == this.rear && tPos != pattern.rear) startPos = null;
                if (startPos != null) {
                    startPos.next.prev = cPos.prev.next = null;
                    startPos.next = cPos;
                    cPos.prev = startPos;
                    for (tPos = list.head.next; tPos != list.rear; tPos = tPos.next) this.insertPrev(tPos.data, cPos);
                    pos = cPos.prev;
                }
                /*else {
                    if (nextPos == null) pos = cPos;
                    else pos = nextPos;
                }
                nextPos = null;*/
            }
            pos = pos.next;
        }
        return this;
    }

    public static void main(String[] args) {
        Integer[] v = {1,2,3,4,1,2,3,1,2,2,1,2,3,1,2,3,4,1,2,3};
        DoublyList<Integer> list = new DoublyList<>(v);
        /*System.out.println(list.toString());
        System.out.println(list.search(new DoublyList<>(new Integer[]{1,2,3,1,2,3})));*/
        System.out.println(new DoublyList<>(list).replaceAll(
                new DoublyList<>(new Integer[]{5,6,7,8}),
                new DoublyList<>(new Integer[]{0,0,0,0}))
        );
        System.out.println(new DoublyList<>(list).replaceAll(
                new DoublyList<>(new Integer[]{1,2,3,7}),
                new DoublyList<>(new Integer[]{0,0,0,0}))
        );
        System.out.println(new DoublyList<>(list).replaceAll(
                new DoublyList<>(new Integer[]{1,2,3}),
                new DoublyList<>(new Integer[]{1,2}))
        );
        System.out.println(new DoublyList<>(list).replaceAll(
                new DoublyList<>(new Integer[]{3,1,2}),
                new DoublyList<>(new Integer[]{5,8,9,0}))
        );
        System.out.println(new DoublyList<>(list).replaceAll(
                new DoublyList<>(new Integer[]{1,2,2,1}),
                new DoublyList<>(new Integer[]{0,0,0,0}))
        );
        System.out.println(new DoublyList<>(list).replaceAll(
                new DoublyList<>(new Integer[]{4,1,2,3}),
                new DoublyList<>(new Integer[]{8,7,6,5}))
        );
        System.out.println(new DoublyList<>(list).replaceAll(
                new DoublyList<>(new Integer[]{2,3,1}),
                new DoublyList<>(new Integer[]{1,2,3,4}))
        );
        System.out.println(new DoublyList<>(list).replaceAll(
                new DoublyList<>(new Integer[]{1,2,3}),
                new DoublyList<>(new Integer[]{1,2,3}))
        );
        System.out.println(new DoublyList<>(list).replaceAll(
                new DoublyList<>(new Integer[]{1,2,3}),
                new DoublyList<Integer>())
        );
    }
}
